home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / zoo / lzc.c < prev    next >
C/C++ Source or Header  |  1980-01-02  |  8KB  |  327 lines
  1. #ifndef LINT
  2. static char sccsid[]="@(#) lzc.c 2.6 88/01/30 18:39:15";
  3. #endif /* LINT */
  4.  
  5. /*
  6. Lempel-Ziv compression.  Mostly based on Tom Pfau's assembly language
  7. code.
  8.  
  9. The contents of this file are hereby released to the public domain.
  10.  
  11.                     -- Rahul Dhesi  1986/12/31
  12. */
  13. #include "options.h"
  14. #include "zoo.h"
  15. #include "zooio.h"
  16. #include "various.h"
  17. #include "zoofns.h"           /* function definitions */
  18. /* zoomem.h defines IN_BUF_SIZE & OUT_BUF_SIZE */
  19. #include "zoomem.h"
  20. #include "debug.h"
  21. #include "assert.h"
  22. /* lzconst.h contains constants for lzd() and lzc() */
  23. #include "lzconst.h"
  24.  
  25. void init_ctab PARMS((void));
  26. void wr_ccode PARMS((int));
  27. int rd_cch PARMS((void));
  28. int lukup_ccode PARMS((int, int, int *));
  29. void ad_ccode PARMS((int, int, int));
  30. void check_ratio PARMS((void));
  31. void flush_c PARMS((int));
  32.  
  33. /* interval at which to check ratio */
  34. #define CHECKGAP 4000
  35. #define NEXT_USE  1
  36. #define FIRST_USE 2
  37. #define FOUND 0
  38.  
  39. struct     tabentry {
  40.    int first;
  41.    int next;
  42.    char z_ch;
  43. };
  44.  
  45. extern char *out_buf_adr;
  46. extern char *in_buf_adr;
  47. extern char memflag;            /* memory allocated? */
  48. struct tabentry *table;         /* this table also used by lzd.c */
  49. static unsigned int free_code;
  50. static int nbits;
  51. static unsigned int max_code;
  52. static unsigned int bitsout;
  53. static int bit_interval;
  54. static unsigned int bytesin, ratio, ratflag;
  55. static unsigned int in_offset, in_size;
  56. static unsigned int bit_offset;
  57.  
  58. #ifdef UNBUF_IO
  59. #define     BLOCKFILE        int
  60. #define     BLOCKREAD        read
  61. #define     BLOCKWRITE        write
  62. int read PARMS ((int, VOIDPTR, unsigned));
  63. int write PARMS ((int, VOIDPTR, unsigned));
  64. #else
  65. #define     BLOCKFILE        ZOOFILE
  66. #define     BLOCKREAD        zooread
  67. #define     BLOCKWRITE        zoowrite
  68. #endif /* UNBUF_IO */
  69.  
  70. static BLOCKFILE in_f, out_f;
  71.  
  72. int lzc (input_f, output_f)
  73. BLOCKFILE input_f, output_f;
  74. {
  75.    int nextch, prefix_code, k;
  76.    int status;
  77.    int where;
  78.  
  79.    in_f = input_f;
  80.    out_f = output_f;
  81.  
  82.    bit_offset = in_offset = in_size = 0;
  83.  
  84.    if (memflag == 0) {
  85.      table = (struct tabentry *) ealloc((MAXMAX+10) * sizeof(struct tabentry));
  86.      memflag++;
  87.    }
  88.  
  89.    init_ctab();
  90.    wr_ccode(CLEAR);
  91.    nextch = rd_cch();
  92.    if (nextch == EOF) {                  /* note real EOF, not Z_EOF */
  93.       wr_ccode (Z_EOF);
  94.         flush_c ((int) ((bit_offset + 7) / 8));
  95.       return (0);                         /* normal return from compress */
  96.    }
  97.  
  98.    /* compression loop begins here with nextch holding the next input char */
  99. loop1:
  100.    if (ratflag != 0)
  101.       check_ratio();
  102.    nextch &= 0xff;             /* turn character to code */
  103.    assert(nextch < 256);
  104. loop2:
  105.    prefix_code = nextch;
  106.    nextch = rd_cch();
  107.    if (nextch == EOF) {                  /* note real EOF, not Z_EOF */
  108.       wr_ccode (prefix_code);
  109.       wr_ccode (Z_EOF);
  110.         flush_c ((int) ((bit_offset + 7) / 8));
  111.       return (0);                         /* normal return from compress */
  112.    }
  113.    nextch &= 0xff;              /* force to 8 bits */
  114.    assert(nextch < 256);
  115.  
  116.    k = nextch;
  117.    status = lukup_ccode (prefix_code, nextch, &where);
  118.    if (status == FOUND) {
  119.       nextch = where;              /* where found */
  120.       goto loop2;
  121.    }
  122.    assert(status == FIRST_USE || status == NEXT_USE);
  123.  
  124.    /* reach here with status = FIRST_USE or NEXT_USE */
  125.    ad_ccode (status, nextch, where);
  126.  
  127.    wr_ccode (prefix_code);
  128.    nextch = k;
  129.  
  130.    if (free_code <= max_code)
  131.       goto loop1;
  132.    assert(nbits >= 9 && nbits <= MAXBITS);
  133.    if (nbits >= MAXBITS) {
  134.    /* To continue using table after it is full, remove next two lines */
  135.       wr_ccode (CLEAR);
  136.       init_ctab();
  137.  
  138.       goto loop1;
  139.    }
  140.  
  141.    nbits++;
  142.    assert(nbits >= 9 && nbits <= MAXBITS);
  143.    max_code = max_code << 1;
  144.    goto loop1;
  145. } /* end lzc() */
  146.  
  147. void wr_ccode (code)
  148. int code;
  149. {
  150.    unsigned int ofs_inbyte, hibits;
  151.    int byte_offset;
  152.  
  153. #ifdef DEBUG
  154. if (code == CLEAR)
  155.    printf(" CLEAR\n");
  156. #endif
  157.  
  158.    assert(nbits >= 9 && nbits <= MAXBITS);
  159.    bitsout += nbits;            /* total number of bits written */
  160.    bit_interval -= nbits;
  161.    if (bit_interval < 0)
  162.       ratflag = 1;            /* time to check ratio */
  163.  
  164.    byte_offset = bit_offset / 8;
  165.    ofs_inbyte = bit_offset % 8;     /* offset within byte */
  166.    bit_offset += nbits;         /* allowing for new code */
  167.  
  168.    if (byte_offset >= OUTBUFSIZ - 4) {
  169.       flush_c (byte_offset);
  170.       bit_offset = ofs_inbyte + nbits;
  171.       out_buf_adr[0] = out_buf_adr [byte_offset];
  172.       byte_offset = 0;
  173.    }
  174.  
  175.    code = code & 0xffff;        /* force to 16 bits */
  176.  
  177.    if (ofs_inbyte == 0)
  178.       out_buf_adr[byte_offset]    = code & 0xff;
  179.    else
  180.       out_buf_adr[byte_offset] |= (code << ofs_inbyte) & 0xff;
  181.  
  182.    hibits = ((unsigned int) code) >> (8 - ofs_inbyte);
  183.    out_buf_adr[byte_offset+1] = hibits & 0xff;
  184.    out_buf_adr[byte_offset+2] = (((unsigned int) hibits) >> 8) & 0xff;
  185.  
  186.    assert(nbits >= 9 && nbits <= MAXBITS);
  187. } /* end wr_ccode() */
  188.  
  189. void init_ctab()
  190. {
  191.    int i;
  192.    bytesin = bitsout = ratio = ratflag = 0;
  193.    bit_interval = CHECKGAP;
  194.    nbits = 9;
  195.    max_code = 512;
  196. #ifdef COMMENT
  197.    for (i = 0; i < 256; i++) {
  198. #endif
  199.    for (i = 0; i < MAXMAX+1; i++) {
  200.       table[i].z_ch = table[i].first = table[i].next = -1;
  201.    }
  202. #ifdef COMMENT
  203.    /*DEBUG*/ table[MAXMAX].first   = table[MAXMAX].next = -1;
  204.    /*DEBUG*/ table[MAXMAX-1].first = table[MAXMAX-1].next = -1;
  205. #endif
  206.    free_code = FIRST_FREE;
  207. } /* end init_ctab() */
  208.  
  209. int rd_cch()
  210. {
  211.    int count;
  212.    bytesin++;
  213.    if (in_offset == in_size) {
  214.       count = BLOCKREAD (in_f, in_buf_adr, INBUFSIZ);
  215.       if (count == -1)
  216.      prterror ('f', "Error reading input file during compression.\n");
  217.       addbfcrc (in_buf_adr, count);
  218.       if (count == 0) {
  219.      debug((printf("\nEOF on input\n")))
  220.      return (EOF);              /* real EOF, not Z_EOF */
  221.       }
  222.       in_size = count;
  223.       debug((printf("\ninput %d chars\n", count)))
  224.       in_offset = 0;
  225.    }
  226.    in_offset++;
  227.    return (in_buf_adr[in_offset-1] & 0xff);
  228. } /* end rd_cch () */
  229.  
  230. void check_ratio()
  231. {
  232. #ifdef COMMENT
  233.    int rat;
  234.    if (bitsout > 16383) {     /* avoid overflow */
  235.       bitsout /= 4;
  236.       bytesin /= 4;
  237.    }
  238.    rat = (2 * bitsout) / bytesin;
  239.    if (1.1 * rat < ratio) {
  240.       printf("#");
  241.       wr_ccode (CLEAR);
  242.       init_ctab();
  243.       bit_interval = CHECKGAP;
  244.       bitsout = 0;
  245.       bytesin = 0;
  246.       ratio = 0;
  247.    } else
  248.       ratio = ((ratio << 2) + ((2 * bitsout) / bytesin)) / 5;
  249. #else
  250.    bit_interval = CHECKGAP;
  251.    bitsout = 0;
  252.    bytesin = 0;
  253. #endif
  254. } /* end check_ratio() */
  255.  
  256. void ad_ccode (status, ch, index)
  257. int status, index, ch;
  258. {
  259.    assert(status == FIRST_USE || status == NEXT_USE);
  260. #ifdef COMMENT
  261.    if (free_code >= MAXMAX)      /* to fix apparent bug in original */
  262.       return;
  263. #endif
  264. #ifdef COMMENT
  265.    if (status == NEXT_USE)
  266.       table[index].next = free_code;
  267.    else         /* else must be FIRST_USE */
  268.       table[index].first = free_code;
  269. #endif
  270.    if (status == NEXT_USE)
  271.       table[index].next = (free_code >= MAXMAX ? -1 : free_code);
  272.    else         /* else must be FIRST_USE */
  273.       table[index].first = (free_code >= MAXMAX ? -1 : free_code);
  274.  
  275. #ifdef COMMENT
  276.    if (free_code < MAXMAX) {
  277. #endif
  278.    if (free_code <= MAXMAX) {
  279.       table[free_code].first = table[free_code].next = -1;
  280.       table[free_code].z_ch = ch & 0xff;
  281.       free_code++;
  282.    }
  283. } /* end ad_ccode() */
  284.  
  285. int lukup_ccode (index, ch, where)
  286. int index;              /* where to start looking */
  287. int ch;                 /* char to look for */
  288. int *where;              /* last entry looked at */
  289. {
  290.    *where = index;
  291.    index = table[index].first;
  292.    if (index == -1) {
  293.       return (FIRST_USE);           /* not found, first use */
  294.    } else {
  295.       while (1) {
  296.      if ((table[index].z_ch & 0xff) == (ch & 0xff)) {
  297.         *where = index;
  298.         return (FOUND);
  299.      }
  300.      *where = index;
  301.      index = table[index].next;
  302.      if (index == -1) {
  303.         return (NEXT_USE);
  304.      }
  305.       } /* end while */
  306.    } /* end else */
  307. } /* end lukup_ccode() */
  308.  
  309. void flush_c (count)
  310. int count;
  311. {
  312.    int status;
  313. #ifdef DEBUG
  314. printf(" <flushed %d bytes> ", count);
  315. #endif
  316.  
  317. #ifdef CHECK_BREAK
  318.     check_break();
  319. #endif
  320.  
  321.     if (count != 0) {
  322.         status = BLOCKWRITE (out_f, out_buf_adr, count);
  323.         if (status == -1)
  324.             prterror ('f', "Error writing during compression.\n");
  325.     }
  326. }
  327.